\documentclass[a4paper]{article}
\usepackage{graphicx}
% Document properties
\date{\today}
\title{Compiler Construction\\Peephole Optimizer for SimpleScalar DLX Assembly Code}
\author
{
  Butrus, Eenass \\
  Liberatore, Lorenzo \\
  Martoidjojo, Gail
}
% http://code.google.com/p/laarwijk-2012-roze/
% Front page without page number and table of contents
\begin{document}
\maketitle
\thispagestyle{empty}
\pagebreak
\tableofcontents
\pagebreak

\abstract
Peephole optimizers have the purpose to optimize code on basic block level.
This report discusses the improvements a peephole optimizer does on basic blocks of \textit{assembly} code in order to reduce the \textit{number of cycles}. Those optimizations are done in phases: first redundant labels, jumps and branches are discared, then the assembly code is being divided into basic blocks. Next, these blocks pass a number of various peephole transformations. The final phase a peephole optimizer may run through is extensive dataflow analysis. 


\section{Introduction}

In this project, ``Compiler Construction'', it is the command to develop a peephole optimizer that optimizes software written assembly code, but derived from C code. Both original and optimized code can be simulated using the SimpleScalar DLX simulator in order to compare the differences.

The optimizer named Peephole Optimizer reads assembly code generated by a cross \verb|gcc| compiler and 
optimizes this code. The output file that is being genereated is now optimized meaning that redundant instructions are removed without destroing the original functionality. The optimized version of the software will then also be simulated with the SimpleScalar DLX simulator.

This report describes the theory behind the Peephole Optimizer written by the lab students, discusses the implementation choices and also the software that constructs the Peephole Optimizer. Furthermore, this report also highlights the testing and the results of this project.

\section{Theory Peephole Optimizer}

The Peephole Optimizer differs from other types of optimizers in the fact that 
it executes on small parts of the code (the so called basic blocks). Basic blocks are 
literally parts of assembly code marked by the very first statement of the assembly code and the first statement following a jump or a branch. Furthermore, the target of a jump or branch (a label) also marks the beginning of a basic block. These markers are called leaders, as they lead a basic block. Logically, basic blocks do not contain more than label which ensures that all instructions inside a basic block are executed sequentially.
The concept of the Peephole Optimizer works on the optimizations problems locally using an approach called ``divide en conquer'' method. 

 % From that small blocks optimizations obtain a global optimization that allow us in the end to optimize it entirely.


\section{Implementation}

\subsection{Used tools}

% ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 

In the first period of this project we were really confused on which programming language we should use
to give birth to this project, after a deep analysis of feasibility study of our group skills and the
amount of time we had to finish it we came to the conlusion that our's optimal solution to do it,
could be only using Python language.
This language even if not known from all the memembers of the group in the beginning has an incredibly fast learning
curve that allowed us to start optimizing almost immediatly thanks to its flexibility, portability and simplicity.
This allowed us also to focus more on the optimizations instead of loosing time on the "how to do it" part.

\subsection{Architecture}

The diagram below gives an overview of the architecture of 
\begin{figure}[htbp] 
	\includegraphics[width=0.3\textwidth]{diagram.png}
	\caption{code design}
	\label{code design}	
\end{figure}

The unoptimized assembly code must first discard redundant branches, labels and jumps in order to create efficient basic blocks in the next phase. This is called global optimization. Because of this, the assembly code is free from unnecessary leaders that leads a basic block, so that the number basic blocks is minimized. 

These blocks are then saved into a list together with the corresponding, and correct, instructions and labels. 

Next, optimizations are performed block-wise (and sequential) because this ensures 

\section{Software}

%In this section explains how the part of the code of tPeephole optimizer has been built,so we will write in detail all the parts of the code and their meaning.
This section discusses the various parts of the code for the optimizer, named ``Peephole Optimizer'', in detail. Not all parts contribute to the concept of ``peephole'' because the initial phase examines the overall assembly code, that is, on global level.

\subsection{Assembly instructions recognizement}

The first things to start with was the Assembly instruction recognizement by the Python code. We thought at this really carefully and we came to the conclusion that the best methods to do it was to use the powerful Phyton code strings management.
Thanks to this we have built up the function ``read\_file(filename)" that reads the file and splits its contents in to two parts. One contains the compiler directives which are the first lines of the assembly code until the keyword ``.ent" and the second part begins after this keyword. he second part of the code 

\subsection{Remove redundant branches}
After reading the assembly code, we will look at specific cases of branches, jumps and labels and remove the redundant one. Therefore, a funcction called ``remove\_redundant\_branches" is built and it is applied only for the assembly code without the compiler directives. In this function we look for four cases: the first one is ``jL1" followed directly with ``L1", in this situation the jump would be removed. The second one checks the accurance labels in sequence, in this case one of the labels will be kept and the labels of all the branches and jumps to the removeed labels will be replaced with the one that is kept. The third one is the accurance of ``beq" followed by ``j", in this case ``bne" will be replaced bij ``bne" and the lable will be that one of the ``j", then the jump will be removed. The last one is the case that a label contains only one instruction and that instruction is ``j", here the label will be removed and all the jumps to this label will be replaced with that one of the jump.

\subsection{Basic blocks}
After removing redundant branches, jumps and labels, the code will be devided into basic blocks. The basic blocks consist of a number of instructions that are excuted sequentially and they can be recognized through the leaders.These leaders are the first statement followed the compiler directives, any statement that is a target of the jump  (a label) and any statement that followes a branch or a jump. This is done by the function ``make\_blocks".

%Logically, basic blocks do not contain more than label which ensures that all instructions inside a basic block are executed sequentially.

\subsection{Local Optimization on Basic Blocks}
These optimization are applied to the code that is divided into basic blocks. Every basic block can contain one or more of this kind of optimization. We have implemented three kind of basic block optimization. 

\begin{enumerate}
\item Copy propagation
After observing the assembly code, we have observed a number of pissible copy propagetion optimizations and then implemented the funtion ``copy\_propagation". First of all is the accurance of ``sw/sb" followed bij ``lw/lb" where in both of these instructions the same register is used, if that is true then ``lw/lb" instruction will be removed. Secondlly is the accurance of ``mov" followed bij ``sw/sb" where the source register of ``sw/sb" is the same as the destination register of the ``mov", in this case the source register of ``sw/sb" will be replacesed by the source register of ``mov" and then remove the instructon ``mov". The last one is the accurence of ``addu, subu, lw, lb, sra" followed bij a ``mov" instruction where the instruction move will copy the destination register of these instructions to another register. Here the instruction ``mov" will be removed if and only if the destination register of ``addu, subu, lw, lb, sra" is being overwritten; the function ``isoverwritten" will examen that. Then the destination register of the instructions mentioned above will be set to that one of the ``mov".

\item Constant folding
We have also observed that in the most of the cases where ``beq/bne" compared two registers or ``addu" and one of these registers contains a number that is loaded befor by the instruction ``li". In this case ``li" will be removed and instead of using the register, the number will be used.

% decided to leave this out because the function now only removes empty lines

%\subsection{Assembly code cleaning}

%Since we've noticed that the code generated was full of unusefull stuff and expensive for the computer such as comments,
%and empty lines we've decided to do delete them from the code giving it a more compact and fast look.
%This has been done creating a simple function that it is used to do that.

\item Optimization Examples by the Assignment%{Local Optimization on Basic Blocks}

This part as the title said talks about all the optimizations that has been made to optimize the code locally on the basics blocks.

\end{enumerate}

\begin{itemize}
\item shift regA\_regA\_0 remove

This optimization has been created since this kind of instruction it's logically unuseful for the code and requires to the computer
an effort of memory and calculation to do this.
So when we find an instruction like this we just delete it because it is unuseful.

\item instr\_regA\_regB\_other

This optimization has been created to change the instructions move regA,regB \& instr regA,regA,... into instr regA,regB,...

\item sw\_regA\_XXX

This optimization has been created to change the instructions sw \$regA,XXX \& ld \$regA,XXX,... into sw \$regA,XXX

\item lw\_XXX\_XregA

This optimization has been created to change the instructions sw add \$regA,\$regA,X \& lw ...,0(\$regA),... into lw ...,X(\$regA)

\item instr\_4\_XXX

This optimization has been created to change the instructions instr \$regA,... \& mov \$4,\$regA \& jal XXX into instr \$4,... \& jal XXX

\item instr\_4\_XXX

\end{itemize}

This optimization has been created to change the instructions instr \$regA,... \& mov \$4,\$regA \& jal XXX into instr \$4,... \& jal XXX

\subsection{Global Optimization \& Dataflow analysis}

The global optimization is
 needed to have better optimizations for the global code because only using the local one there are some
problems that cannot be solved.

\begin{itemize}
\item poplist\_from\_index\_for\_numelem
This function it's a simple function that permits us to pop out from a list you choose a number of elements.

\item jump\_to\_line
This function it's used whenever in the code we find a jump it basically goes where the jump tells it to go.

\item branch\_to\_line
This function it's used whenever in the code we find a branch it basically goes where the branch results tells it to go.

\item pop\_dead\_registers
This function it's used to take track of the register used and the dead register which are not used anymore.

\item dataflow\_analysis
It's the function that permits to do pratically the dataflow analysis keeping traks of the registers and the flow of the code.

\item mips\_operations
This function it's used to uderstand the various mips operations and to keep track of them during the dataflow analysis.

\item register\_value
This function it's used see wich registers are actually used and what's inside them.

\item move\_regA\_regB
This function it's used to optimize the code, basically if two register has the same value and there's a move between them
it erase that instruction beacuse it's useless in terms of coding.

\item search\_element
This function it's useful to find an element into a multidimensional list.

\item optimized\_list
This function create a list with the optimized files instructions.

\item optimized\_list\_into\_file
This function create a file with the optimized instructions that are in the list.

\item peephole\_optimizer
This is the main function that permits optimizations in the code using all the functions described before.

\end{itemize}

\section{Testing}

In order to test the Peephole Optimizer a benchmark suite, files containing C code, was provided by the lab assistant. From those files assembly code can be generated using the cross gcc compiler with following command:

\begin{verbatim}
xgcc -S benchmark.c
\end{verbatim}

The output file then is a benchmark.s file where the .s indicates that the file contains assembly code. %To use the Peephole optimizer the assembly code generated by the machine the command you have to use to do it is:
To use the Peephole optimizer the following command can be given to the terminal:

\begin{verbatim}
python peephole.py benchmark.s output.s
\end{verbatim}

Prerequisites for running this program having python installed on your machine. Python, if not already
installed, can be downloaded from {\tt www.python.org}. Python version 2.7 is recommended.

\section{Results}


The table below illustrates the results obtained by testing the peephole optimizer with the benchmark suite provided by the lab assistant.
The percentages, in terms of number of cycles, are calculated as follow:\\
\\
\\$\frac{\textnormal{original - after optimization}}{\textnormal{original}} \times \textnormal{100\%}$

\begin{table}[htbp]
	\centering
\begin{tabular}{|c|c|c|c|}
\hline
Benchmark & Original number of cycles & Number of cycles after Optimization & Speedup in  \% \\ \hline
pi.s & 33470 & 33455 & 0.044 \% \\ \hline
acron.s & 4436526 & 4877378 & -9,936\% \\\hline
whet.s & 2865472 & 2850289 & 0,529 \% \\\hline
dhrystone.s & 2888237 & 2813315 & 2,594 \% \\\hline
clinpack.s & 1553761 & 1544048 & 0,625 \%  \\ \hline
slalom.s & 63805406 & 63244553 & 0,879 \% \\ \hline
\end{tabular}
	\caption{benchmark suite}
	\label{benchmark suite}
\end{table}

Benchmark pi.s needs user input for the number of iterations and for testing ``8'' is chosen.  
The results for slalom.s are obtained by choosing 6 as the number of seconds that is the goal and the variable``n'' is bounded by 12 and 45. 


\section{Group Management}

To complete our project we split the work in subproblems such as parts of the code to be written individually
,the test phase of the benchmarks and also to write this document. We all wrote the different parts.
Since this project was done by three persons the things to do has been splitted in three, in this way we could do it
faster.
For all this phases, of course, in the end has been predicted another phase that would help us to stick toghether 
all the separated parts creating in the end one big project.

The persons in the group came from different backgrounds and different universities so we choosed to use internet
as a tool to create our project, since in most cases our "free time" to do this project does not match at all.
So all the work basically has been done at home, by email or using a repository online and on the labs or when we
were more free we met each other to test it or to talk about this.

\section{Future improvements}

\section{Conclusion}

\section{References}

\end{document}
